Complete Linux/Complete Linux.iso/docs/apps/database/postgres/postgre2.z/postgre2/doc/implementation/planner/3.design

Text File | 1992-08-27 | 48.5 KB | 1,248 lines

.sh 1 "DESIGN OF THE OPTIMIZER" 3
.pp
This section will first describe the optimization algorithm chosen
for POSTGRES, focusing on features specifically incorporated to handle
extendibility in POSTGRES.
The rest of the section will then indicate how this algorithm
is used in optimizing nested-attribute queries.
Algorithms are described in high-level detail with special attention given
to the design rationale behind various features.
Plans produced by these algorithms are also described to indicate
how the query processor interprets optimizer plans.
.sh 2 "Choice of Optimization Algorithm"
.pp
In selecting an optimization algorithm to work with, there were two choices \*-
query decomposition [WONG76] or exhaustive search.
Query decomposition is a heuristic \*(lqgreedy\*(rq algorithm that
proceeds in a stepwise fashion.
If a query has three or more variables, heuristics are first
used to subdivide the query into two smaller subqueries.
This process is applied recursively to any subqueries that contain
at least three variables.
For subqueries containing less than three variables, tuple substitution is
used to process the join, while a component known as the one-variable query
processor determines the path used to scan individual relations.
.pp
Once the first step of a query plan has been constructed using this
decomposition algorithm, the step is executed.
By doing this, the optimizer has information on the sizes of
intermediate results,
which can be used to its advantage in making subsequent decisions.
Furthermore, the search space is reduced substantially because only a
single path is considered.
However, as a result, potentially good plans
are ignored during early stages of the algorithm.
.pp
The SYSTEM-R designers took a dramatically
different approach by essentially doing an exhaustive search of
the plan space.
All possible ways of scanning each relation appearing within a query are
found.
Using these paths, all plans for processing two-way joins are considered.
Then, single relations are joined to form three-way joins, and
from here, the algorithm iterates in a similar manner.
The cost of executing each of these paths is estimated, and the cheapest is
selected as the desired plan.
.pp
Although exhaustive search inevitably requires more planning time,
good plans are not overlooked.
This is especially important when optimizing complicated queries
because for these queries the difference in the amount of processing
required by two plans can be quite significant.
Thus, the extra planning overhead is more than compensated
by savings that result from executing a better plan.
For simple queries, although the selected plan may not be
significantly better than
another, the extra overhead is likely to be inconsequential.
For queries embedded within data fields, the extra overhead of enumerative
planning is especially unimportant because these queries will be
preexecuted in background mode and POSTGRES will cache
the execution results as well as the compiled query plans.
In these cases, the time
spent optimizing will be amortized over several executions.
.pp
The SYSTEM-R optimizer only considers linear joins, e.g.,
.(l
((A join B) join C) join D
.)l
for a 4-way join.
The optimizer could be improved to consider joins between pairs of
composite relations, e.g.,
.(l
(A join B) join (C join D).
.)l
This would allow the optimizer to examine further plans, and on occasion,
these plans may be
significantly better than plans that only utilize linear joins.
.pp
Another enhancement to the SYSTEM-R optimizer is to consider plans that
will dynamically create indices
on join attributes if they are not already available.
If the cost of building the index is small compared to the savings that
result from using the index in a join, such a strategy can be advantageous.
.pp
The POSTGRES optimizer does not consider these enhancements either.
Although they would undoubtedly result in a better optimizer,
the main goal of POSTGRES is to illustrate the feasibility of the novel
features that it will support.
Therefore, for simplicity, the POSTGRES optimizer will adhere fairly closely
to the algorithm as described in [SELI79].
.sh 2 "Pipelining of Tuples"
.pp
Ignoring nested attributes for the moment, the query plan created by the
optimizer is a tree of scan and join nodes.
Relations are either scanned sequentially or via primary or secondary
indices.
Joins are processed using nested iteration, merge-sorts, or hash-joins.
Each of these join strategies will be discussed further in section 3.3.3.
.pp
Every join involves two components.
The component that is scanned first will be referred from hereon as the
\*(lqouter join relation,\*(rq while the other component is
the \*(lqinner join relation.\*(rq
For a query containing \fIn\fR variables, the plan
is constructed in such a way that the \fIn\fR-way composite join
appears at the top of the tree.
(See figure 3.1.)
.(z
.hl
.GS
file figure3.1
.GE
.sp
.ce
.sz \n(ep
(((A1 join A2) join A3) join ... A(n-1)) join An
.sz \n(pp
.sp
.ce 2
\fBFigure 3.1\fR
Plan tree for an \fIn\fR-way join
.hl
.)z
The left subtree is a plan
for processing the outer join relation, and the right subtree corresponds
to a plan for processing the inner join relation.
Because the optimizer only considers linear joins (see section 3.1),
the right subtree is always a scan
node while the left subtree is a plan for an \fI(n-1)\fR-way join, or
scan if \fIn\fR = 2.
These characteristics apply recursively to the rest of the tree.
.pp
To process such a plan, the query processor walks through the tree starting
at the root.
If the node is a join, depending on the join strategy, calls are made on
either the left or right subtrees to retrieve tuples from either the
outer or inner join relations.
If the node is a scan node, the appropriate relation is scanned using
the selected strategy.
When scanning a relation, restriction clauses specified on the relation
are examined.
Once a single tuple has been found satisfying these qualifications, the
tuple is returned to the node that initiated the scan.
If the higher node was a join node and this tuple originated from the
left subtree of the join node, then a call is made on the right subtree.
Otherwise, this tuple originated from the right subtree and thus can be
joined with the tuple passed back by the left subtree.
Provided
all corresponding join clauses are satisfied, a composite tuple is formed.
If the join clauses are not satisfied, calls are made on either the right
or left subtrees until a qualifying composite tuple can be constructed.
Once this composite tuple is formed, it is passed upward to the node that called
this join node, and the process is repeated.
.pp
If tuples must be sorted or hashed prior to join processing (see figure 3.2),
all tuples returned from a lower node must first be stored in a temporary
relation.
.(z
.hl
.GS
file figure3.2
.GE
.sp
.ce 2
\fBFigure 3.2\fR
Sort node in a plan tree
.hl
.)z
Once the lower node has passed all relevant tuples into the temporary,
the sort or hash is performed.
From here, the temporary relation is scanned like any other relation,
and its tuples are also pipelined upward.
In summary,
calls are made on lower nodes in the tree when tuples are needed at higher nodes
to continue processing, and
tuples originating from scan nodes at the leaves of the
plan tree are pipelined bottom-up to form composite tuples, which also are
pipelined upward.
.pp
As an alternative to pipelining, the query executor could have processed
nodes to completion,
stored the intermediate subresults in temporary relations,
and then passed groups of
tuples upwards rather than a tuple at a time.
This may be advantageous when there are many duplicate tuples in a subresult.
The duplicates could be removed from the temporary, reducing the time
required to process later joins.
However, for simplicity, we chose to focus on a pipeline processing scheme for
now.
Implementation of temporaries will be reserved for future extensions.
.pp
.sh 2 "Generating Possible Plans"
.pp
The SYSTEM-R optimizer decides which plans should be generated
based upon
the types of indices defined on relations appearing in a query as well
operators that also appear in the query.
For example, suppose a B-tree index is defined on a relation, and
a query contains the following restriction clause:
.(l
\fIrelation.field OPR constant\fR.
.)l
Using Selinger's notation, clauses of this form will be referred from
hereon as \*(lqsargable\*(rq clauses [SELI79].
If \fIrelation.field\fR within a sargable clause happens to match the
key of the B-tree index and
the restriction operator, \fIOPR\fR, is anything but
$!=$, then an index path should be considered because a B-tree provides
efficient access when used with the following operators:
.(l
=, <, $<=$, >, $>=$.
.)l
The criteria for decisions like this can easily be
incorporated into the SYSTEM-R optimization code
because a conventional database only has a fixed number of operators
and access methods;
so there are only a fixed number of possibilities.
Clearly the POSTGRES optimizer cannot use such a strategy due to
POSTGRES's provision for extendibility.
Therefore, we resorted to storing operator and access method characteristics
in database system catalogs, and we coded the optimizer to access and use
this information in generating possible plans.
The rest of this subsection will discuss in greater detail the steps
taken in creating access plans in order to focus on the type of information
the optimizer and other relevant parts of the system will need in
making decisions.
.sh 3 "Transforming Queries Into Standard Form"
.pp
Prior to optimizing a query, the parser must take the user's ascii request,
parse it for valid syntax, perform semantic checks,
and finally generate a tree representing information within the query.
To make optimization simpler and to produce more efficient
query plans, the parser must place the qualification portion of every
query in conjunctive normal form.
This entails pushing all \*(lqor\*(rq clauses to the innermost levels
of a qualification using the following distributive rule:
.(l
a or ( b and c ) $==$ ( a or b ) and ( a or c ).
.)l
The optimizer also requires that \*(lqnot's\*(rq be pushed to the innermost
levels using DeMorgan's law:
.(l
not ( a and b ) $==$ not ( a ) or not ( b )
not ( a or b ) $==$ not ( a ) and not ( b )
.)l
and if possible, removed from the query.
For example, the qualification in figure 3.3 is equivalent to the
qualification in figure 3.5, which is in conjunctive normal form with
\*(lqnot's\*(rq removed.
.(z
.hl
.(l C
.sz \n(ep
not ( r.f = 1 ) or ( not ( r.f2 > 1 or r.f2 < 3 ))
.sz \n(pp
.sp
\fBFigure 3.3\fR
Qualification in non-standard form
.sp 2
.sz \n(ep
( not ( r.f = 1 ) or not ( r.f2 > 1 )) and ( not ( r.f = 1 ) or not ( r.f2 < 3 ))
.sz \n(pp
.sp
\fBFigure 3.4\fR
Equivalent qualification in conjunctive normal form
.sp 2
.sz \n(ep
( r.f $!=$ 1 or r.f2 $<=$ 1 ) and ( r.f $!=$ 1 or r.f2 $>=$ 3 )
.sz \n(pp
.sp
\fBFigure 3.5\fR
Equivalent qualification in conjunctive normal form with \*(lqnot's\*(rq removed
.)l
.hl
.)z
.pp
Removing \*(lqnot's\*(rq from a qualification
requires substituting operators with their respective negations.
For example, \*(lq=\*(rq would be replaced by \*(lq$!=$,\*(rq while
\*(lqAREAGT\*(rq would be replaced by \*(lqAREALE.\*(rq
For the parser to make these substitutions,
users must specify an operator's
corresponding negation, in addition to other information, when defining
a new operator.
The information is specified as follows:
.(l
\fBdefine operator\fR (\fBopname is\fR =, $...$, \fBnegator is\fR $!=$, $...$)
.)l
and is stored in an operator catalog, accessible by
the parser.
.pp
There are, however, problems associated with this requirement.
First of all, this \fIforces\fR users to define operators
corresponding to negators.
In other words, having specified \*(lqAREANEQ\*(rq as a negator, it is also
necessary to define an operator called \*(lqAREANEQ.\*(rq
Although this definition is not difficult, since a negator is
the logical opposite of an already defined operator, users may have
no need for the negator, and therefore would rather not have defined
the extraneous operator.
Secondly, because every negator is also a user-defined operator, an
operator's negator may be specified before the negation operator has been
defined.
In other words, depending on whether the operator \*(lqAREAEQ\*(rq
or \*(lqAREANEQ\*(rq
is defined first, the other operator will not have been defined yet
when the negator of the first is specified.
This means there is no guarantee that the specified
negator is actually a valid operator;
a user could specify the negator of \*(lqAREAEQ\*(rq to be \*(lqfoobar,\*(rq
or he may specify the correct negator, \*(lqAREANEQ,\*(rq but forget to
define the \fIoperator\fR \*(lqAREANEQ.\*(rq
.pp
We have addressed both issues by implementing the optimizer so it allows
\*(lqnot's\*(rq to appear within qualifications.
Therefore, if a user defines a negator that happens to be a nonexistent
operator (e.g., \*(lqfoobar\*(rq) or doesn't specify one,
the parser has no choice but to push the \*(lqnot's\*(rq as far as possible
into the qualification without actually removing them.
(See figure 3.4.)
The only problem with this is that the optimizer may not produce
optimal plans when \*(lqnot's\*(rq are left within clauses.
For example, the following query:
.(l
(1) \fBretrieve\fR (foo.bar) \fBwhere not\fR(foo.f1 AREANEQ 1)
.)l
is equivalent to this query:
.(l
(2)  \fBretrieve\fR (foo.bar) \fBwhere\fR foo.f1 AREAEQ 1
.)l
because \fBnot\fR(AREANEQ) $==$ AREAEQ.
If an area B-tree index is defined on the field \*(lqf1,\*(rq
then the optimizer would definitely consider an index scan because the operator,
\*(lqAREAEQ,\*(rq in query (2) can be used with an area B-tree.
However, if a user had not specified the negation of \*(lqAREANEQ,\*(rq
then the transformation from (1) to (2) would not have been possible,
and the optimizer could not have considered an index scan.
In this case, the index scan probably
would have been the optimal path.
Therefore, it is to the user's advantage to specify and define negators.
.pp
Another desirable transformation is that variables in
qualifications appear on the left-hand side of an operator and constants
on the right (e.g., \fIr.field OPR constant\fR).
To make this transformation, operands must be reversed and operators
must be replaced with their respective
\*(lqcommutators,\*(rq which again the user must specify.
For example, the commutator of \*(lq<\*(rq is \*(lq>,\*(rq while the
commutator of \*(lqAREAEQ\*(rq is also \*(lqAREAEQ.\*(rq
The issues and solution discussed in the previous paragraphs in
reference to negators also apply here, and
again, it is to the user's advantage to specify commutators.
The reasoning behind this will be discussed further in section 3.3.2.
Basically, it enables the optimizer to consider index paths
it could not have considered had a variable appeared on the right hand
side of an operator.
.sh 3 "Index Scans"
.pp
Once a query tree has been transformed as close as possible to standard form,
it is passed to the optimizer.
The first step the optimizer takes is to find all feasible paths for
scanning each relation appearing in the query.
Relations can always be scanned sequentially;
therefore, a sequential scan path is always considered.
Generally when sargable clauses (i.e., clauses of the form
\fIrelation.field OPR constant\fR)
appear within queries,
indices will restrict the amount of search required.
Therefore, if a user has a primary index or secondary indices
defined on a relation, all viable index paths are also considered.
.pp
For an index to be considered, its keys must match variables
that appear within sargable restrictions.
The optimizer also needs to insure the usability of the operator within
the sargable clause with the index under consideration.
For example, an area B-tree, whose records are sorted in \*(lqAREALT\*(rq order,
can be used with sargable clauses for which \fIOPR\fR is:
.(l
AREAEQ, AREAGT, AREAGE, AREALT, or AREALE,
.)l
while a standard B-tree can be used with sargable clauses containing:
.(l
=, >, $>=$, <, or $<=$.
.)l
To distinguish the two cases, POSTGRES introduces the
notion of a \*(lqclass.\*(rq
Associated with every class is a particular access method and the set of
operators that can be used with it.
For example, the class \*(lqintops\*(rq refers to a standard B-tree.
The operators associated with it are:
.(l
=, >, $>=$, <, and $<=$.
.)l
The class \*(lqareaops\*(rq is an area B-tree.
Therefore, the operators associated with it are:
.(l
AREAEQ, AREAGT, AREAGE, AREALT, and AREALE.
.)l
Moreover, another class \*(lqhashops\*(rq is a standard hash table that
can only be used with \*(lq=\*(rq.
This information is stored as specified in table 3.1.
.(z
.hl
.sz \n(ep
.TS
center;
|c||c|c|c|c|
c ||c|c|c|c|.
_
AMOP    access-method    class    operator    $...$ other information $...$
_
    B-tree    intops    =
    B-tree    intops     <
    B-tree    intops    \(<=
    B-tree    intops    >
    B-tree    intops    \(>=
    B-tree    areaops    AREAEQ
    B-tree    areaops    AREALT
    B-tree    areaops    AREALE
    B-tree    areaops    AREAGT
    B-tree    areaops    AREAGE
    hash    hashops    =
    _    _    _    _
.TE
.sz \n(pp
.sp
.ce 2
\fBTable 3.1\fR
Index and operator classes
.hl
.)z
To determine the usability of an index, whose key matches the variable
within a sargable clause, table 3.1
is scanned using the class of the index and the operator within the
sargable clause as a search key.
If the pair is found, then the index can be used; otherwise, it cannot.
.pp
Determining index usability, therefore, involves matching operators that appear
within sargable restriction clauses with the operators associated with
an index's class.
By requiring that qualifications be transformed so variables are
on the left-hand side and constants are on the right-hand side,
the optimizer is insured that an operator appearing within a
clause is semantically equivalent
to the actual operator that appears in table 3.1.
For example, suppose the operator \*(lqfoo\*(rq is usable with index
\*(lqfoobar,\*(rq but its commutator \*(lqbar\*(rq is not.
If we have the following restriction:
.(l
10 foo relation.field,
.)l
the optimizer should not consider using index \*(lqfoobar\*(rq because the above
restriction is equivalent to:
.(l
relation.field bar 10.
.)l
.pp
Currently, only a single clause can be used with an index defined on a single
key.
For example, if the following two clauses are contained in a query:
.(l
r.foo > 100 \fBand\fR r.foo < 150,
.)l
and a B-tree index is defined on the field \*(lqfoo,\*(rq then
only one of the two clauses can be used with the index.
In other words, either \fIall\fR values foo > 100 are located using the
index, or \fIall\fR values < 150, but \fInot\fR both.
Had both clauses been used with the index, only those values between
100 and 150 would have to be examined.
This has the possibility of reducing the scope of an index
scan substantially.
However, such an optimization is being reserved for
future extensions of POSTGRES.
It will not only require a
a redefinition of the access method interface
but also extra information from the user establishing which operator should
be used at the low end of a scan (e.g., >) and which corresponds to
the high end (e.g., <).
The first requirement is necessary because currently the access
method interface is only
designed to work with one clause per index key.
.pp
In the case where an index is defined on multiple keys,
the ideas discussed above simply generalize.
In other words, for every key of an index, there must be a corresponding
sargable restriction clause, and
in addition to all operators in these
clauses being usable by the index, they all must be identical.
A more flexible approach would have allowed partial matching of keys
and multiple operators to be used in a single scan.
This would have required that POSTGRES store further information about operators
and access methods in system catalogs.
Namely, for every access method, the optimizer would need an indication
as to whether partial key matching is possible, and
it also would need some way of establishing that the following
clause:
.(l
r.field1 = 1 \fBand\fR r.field2 > 5
.)l
can be used with a B-tree index defined on \*(lqfield1\*(rq
and \*(lqfield2,\*(rq but the following cannot:
.(l
r.field1 > 1 \fBand\fR r.field2 < 10.
.)l
The benefits of this extra information is not significant
enough to justify the extra complexity that would be
required when defining new operators and access methods;
therefore, POSTGRES does not implement these features.
.pp
One optimization that the POSTGRES planner does support is use of
multiple indices to process \*(lqor\*(rq clauses.
Normally, it would not be possible to use an index scan with the
following clause:
.(l
r.field = 1 \fBor\fR r.field = 2
.)l
because there are two key values, 1 and 2.
However, it is possible to use an index scan keyed on 1 followed by
another index scan keyed on 2.
Since two index scans may be much less expensive than a single sequential scan,
the optimizer will consider using multiple index scans.
.pp
In addition to restricting the scope of a search, index paths are also
considered for another reason.
During query processing, it may be necessary to sort an intermediate
result prior to a merge-sort join (see figure 3.2), or the user may
specify that the results of
a retrieve query be sorted on certain fields.
However, these sorts do not have to performed explicitly at all times.
Some access methods maintain their tuples sorted on the keys
used to define the structure.
Thus, scanning a relation via such an index may yield tuples sorted in a
desired order.
For example, a standard B-tree stores its tuples sorted either in
ascending (<) or descending (>) order, while an area B-tree maintains its
tuples sorted in either \*(lqAREALT\*(rq or \*(lqAREAGT\*(rq order.
.pp
To make use of an index with this sort characteristic,
the index keys must either
match variables within join clauses, which correspond to relations
that will later be merge-sorted, or attribute fields on which
a query's resulting tuples will be sorted.
To determine whether an index's
implicit sort order is that which is needed, POSTGRES requires
that users specify an access method's sort order (if it exists) when defining a
new access method.
If the implicit ordering matches a desired ordering and the keys are usable,
a path that takes advantage of the index will be considered.
The next two subsections will elaborate on further uses of this sort
information.
.sh 3 "Join Paths"
.pp
Once all feasible paths have been found for scanning single relations,
paths are found for joining relations.
Joins are first considered between every two relations for which there
exists a corresponding join clause.
For example, for the following query:
.(l
\fBretrieve\fR (A.a, B.b, C.c) \fBwhere\fR A.d = B.e,
.)l
during the first level of join processing, the only pairs considered are:
.(l
A join B
B join A
.)l
All feasible paths are found for processing joins between these relation
pairs.
Having done this, all paths are then found for processing 3-way joins,
using available 2-way join paths for the outer
path and relation scan paths for the inner path.
Again, the optimizer only considers those join pairs for which there is
a corresponding join clause.
If this heuristic results in no further relations being joined,
all remaining possibilities are considered.
For the above query, at the second level of join processing, no relations
should be joined according to the heuristic.
Therefore, the remaining possibilities are:
.(l
(A join B) join C
(B join A) join C
.)l
From here, these steps are repeated until no further join levels need
to be processed.
.pp
All possible join paths are generated for every join pair considered.
The simplest join strategy is nested iteration.
In a nested iteration join, the inner join relation is scanned once
for every tuple found in the outer join relation.
All available paths on the outer join relation are possibilities
for the outer path.
On the other hand, since the inner join path is independent of
the outer in a nested iteration join,
only the least expensive path for the inner join relation is a
possibility for the inner path.
.pp
Nested iteration is simple, but it can be a time-consuming join strategy,
especially if the inner join relation is not indexed on join
variables.
A join strategy that is much more attractive in these situations is merge-sort.
A merge-sort join can be used to process a join between
\fIrelation1\fR and \fIrelation2\fR,
provided there is a merge join clause of the form:
.(l
\fIrelation1.field1 OPR relation2.field2\fR.
.)l
During the first phase of a merge-sort, each relation is sorted on
appropriate join attributes.
During the second phase, the merge phase, the two relations
are merged together, taking
advantage of the fact that both relations are ordered on join attributes.
.pp
For a merge-sort join to be advantageous,
the operator within a merge join clause must be
\*(lqsimilar to\*(rq an equality operator, e.g. \*(lqAREAEQ\*(rq.
Therefore, in the most ideal situation, when both join relations contain
unique values in the merge join fields, the merge phase will only require
a sequential scan of both sorted relations.
So when defining new operators, POSTGRES requires that users indicate
whether an operator is \*(lqmergesortable\*(rq by specifying the
operator that must be used to sort the two join relations prior to
the merge.
For example, \*(lq=\*(rq is mergesortable, provided the sort is made in
\*(lq<\*(rq order, while \*(lqAREAEQ\*(rq is also mergesortable,
provided the sort is in \*(lqAREALT\*(rq order.
Therefore, if a join clause in the form specified above
contains a mergesortable operator, then a merge-sort join
path between the two relations in the clause is considered in addition to
paths that process the join using nested iteration.
.pp
As alluded to earlier, relations may not always have to be explicitly sorted
prior to a merge.
If the keys of an index match join attributes and
the index's implicit sort order
matches the sort operator required for the merge,
the relation need not be sorted;
unless, of course, it is cheaper to scan a relation into a temporary
via its least expensive path, sort the temporary, and then read the
sort result.
.pp
A second join strategy that may be useful when indices are not available
is hash-join.
To process a join using this strategy, the inner join relation is first
hashed on its join attributes.
Then, the outer relation is scanned.
For every tuple found, values within outer join attributes are used as
hash keys to locate tuples in the inner join relation.
Thus, to use such a strategy, the join operator also must be
\*(lqsimilar to\*(rq an equality operator.
Users will indicate this by simply specifying whether an operator
is \*(lqhashjoinable\*(rq when defining a new operator.
.sh 3 "Pruning The Plan Space"
.pp
In generating possible plans for a query, many paths are considered.
In fact, the plan space is exponential because
plans at lower levels are used in creating plans at higher levels.
Furthermore, when indices and multiple join strategies can be used,
there are a number of ways of processing scans and joins on
identical relations.
Moreover, some of these paths may be redundant.
.pp
Two paths are redundant if they scan identical relations, and their
resulting tuples are sorted on identical fields.
The latter is determined by making use of
index sort information.
For example, suppose the outer relation of a join is scanned using an index
that sorts its tuples in ascending order, and the relation is joined
with another relation using nested iteration.
This join path is equivalent to another path where
the outer relation is explicitly sorted into ascending order and
merge-sorted with the same inner join relation.
Although these two paths are different, they will yield identical results
because both outer join relations are sorted in identical order, and
joins preserve the sort order of the outer relation.
Therefore, after generating plans for each level of joins,
if two redundant join plans are found, the optimizer can eliminate the
more expensive of the two, thereby reducing the size
of the plan space.
.sh 2 "Estimating Costs and Sizes"
.pp
To prune the plan space as well as determine the optimal plan,
the optimizer must estimate the cost of
executing every plan it generates.
In the SYSTEM-R optimizer,
both CPU and I/O time are accounted for in estimating costs.
Every cost factor is of the form:
.(l
cost = P + W * T,
.)l
where \fIP\fR is the number of pages examined at runtime by a plan and
\fIT\fR is the number of tuples examined.
\fIP\fR reflects I/O cost, \fIT\fR reflects CPU cost,
and \fIW\fR is a weighting factor that indicates the relative importance of
I/O to CPU in terms of processing cost.
Thus, for a sequential scan of a relation,
since every page and tuple must be examined,
\fIP\fR equals the number of
pages in the relation and \fIT\fR equals the number of tuples.
For a secondary index scan, the number of pages and tuples touched also
depends on the number of pages and tuples in the index relation
because index pages and tuples must be read first to determine where to
scan in the main relation.
.pp
For every index,
the number of pages and tuples touched is also determined by
the fraction of tuples in a relation that one would expect to satisfy
restriction clauses specified on the relation.
This fractional quantity is called a \*(lqselectivity.\*(rq
Selectivities are functions of a variety of parameters,
including the operator in the restriction clause, the restriction constant,
the number of records in an index, and the maximum and minimum values
of entries stored in an attribute.
In SYSTEM-R, every possible selectivity factor is
hardwired into the cost estimation code.
See table 3.2 for a sampling of selectivity factors.
.(z
.hl
.sz \n(ep
.TS
center box;
c|c
l|l.
qualification    selectivity factor
=
r.field = value    1/(number of tuples in the index relation defined on r.field)
_
r.field > value    ((high value of r.field) - value) /
    ((high value of r.field) - (low value of r.field))
_
r.field < value    (value - (low value of r.field))/
    ((high value of r.field) - (low value of on r.field))
.TE
.sz \n(pp
.sp
.ce 2
\fBTable 3.2\fR
Examples of selectivity factors for SYSTEM-R
.hl
.)z
.pp
Cost estimation formulas for all join strategies are functions of the sizes,
in pages and tuples, of the outer and inner join relations.
To estimate the size of either an outer or inner join relation, the optimizer
simply multiplies the original size of the relation by the selectivity
of every restriction clause applicable to the relation.
If the clause can be used with an index, the selectivity is computed
as described earlier.
If it cannot, SYSTEM-R resorts to an \*(lqelse case,\*(rq
associating constants with these factors.
The SYSTEM-R designers justify this simplification by stating that if an index
is not defined on
a relation, this implies that the relation is small; so if the
selectivity is not accurate, the difference is insignificant.
If the outer join relation is a composite relation, the desired
selectivity is that of a join operation.
Such a selectivity indicates the fraction
from among the cross product of an outer and inner join relation
one would expect to satisfy a join clause.
Again, SYSTEM-R hardwires this information into the optimizer code.
For a summary of the different cost formulas required, see table 3.3.
.(z
.hl
.sz \n(ep
.TS
center box;
c s s
c|c|c
l|l|l.
Cost of Scans
=
    P    T
_
Sequential Scan    NumPages    NumTuples
_
Primary Index Scan    NumPages*F    NumTuples*F
_
Secondary Index Scan    NumPages*F + ITuples*F    ITuples*F + NumTuples*F
.TE
.sp
\fIwhere\fR
.in +0.5i
.nf
NumPages = the number of pages in a relation
NumTuples = the number of tuples in a relation
ITuples = the number of tuples in an index relation
F = combined selectivity factor of applicable restriction clauses
.fi
.in -0.5i
.sp
.ce
.TS
center box;
c s
l|l.
Cost of Joins
=
Nested Iteration    $C sub outer + N sub outer * C sub inner$
_
Merge-sort    $C sub outer + C sub sortouter + C sub inner + C sub sortinner$
_
Hash-join    $C sub outer + C sub createhash + N sub outer * C sub hash$
.TE
.sp
\fIwhere\fR
.in +0.5i
.nf
$C sub outer$ = the cost of scanning the outer join relation
$C sub inner$ = the cost of scanning the inner join relation
$C sub sortouter$ = the cost of sorting the outer join relation into a temporary$" " sup \(dg$
$C sub sortinner$ = the cost of sorting the inner join relation into a temporary$" " sup \(dg$
$C sub createhash$ = the cost of hashing the inner join relation into a temporary
$C sub hash$ = the cost of a single hash
$N sub outer$ = the size of the outer join relation
.fi
.in -0.5i
.sp 2
.nf
.sz \n(fp
$" " sup \(dg$ equals 0 if sort is not required
.sz \n(pp
.fi
.sp
.ce 2
\fBTable 3.3\fR
Summary of cost formulas
.hl
.)z
.pp
The POSTGRES optimizer uses this same basic idea in estimating
costs.
As in SYSTEM-R, the system stores statistical information that cost formulas
depend upon in database system catalogs.
However, POSTGRES takes the novel approach of updating certain
statistics, like
the number of pages and tuples in relations, using demons, which execute
in background mode.
These demons are implemented using triggers, a feature
POSTGRES supports.
Another new idea is that other statistics, e.g., the high and low values
of an attribute, are stored in the form of queries embedded within
data fields.
These queries will retrieve appropriate information from elsewhere
in the database, and the system will cache the result so the optimizer
need not repeatedly execute the same query.
These two provisions alleviate problems other systems encountered when
updating database statistics.
INGRES updated statistics immediately, resulting in loss of concurrency
because it blocked other
users access to information in system catalogs.
SYSTEM-R chose not to update statistics at runtime, instead requiring
that a data base administrator run a special command to explicitly do
the update.
This, however, meant that statistics were not always up-to-date,
possibly yielding incorrect cost estimations.
.pp
To account for all possible selectivities, the approach of storing
information in catalogs is used again.
One difference between selectivity information and other operator and
access method
information seen thus far is that selectivities are parameter
dependent, as illustrated in table 3.2.
An earlier approach suggested storing simple formulas within data fields
and writing a parser to interpret the formula, substituting appropriate
values for a fixed set of possible parameters [STON85a].
This is fairly straightforward, but not very flexible.
Instead, our optimizer capitalizes on an inherent feature of POSTGRES.
As already mentioned, POSTGRES supports
embedding of queries within data fields.
Generalizing on this idea, POSTGRES also allows users to define
arbitrary procedures
written in general purpose programming languages, like C and LISP,
which can then be registered into the system and
stored within data fields [STON86c].
Therefore, in POSTGRES every selectivity formula is expressed
using a parameterized procedure.
Each procedure accepts as its arguments the relations,
attributes, and constants
appearing within restrictions and the index identifier and number of index
keys, if an index is used.
The routine then retrieves necessary information
from elsewhere in the database and returns a computed selectivity.
.pp
As discussed in reference to SYSTEM-R selectivities, selectivities come
in three flavors.
Therefore, there will be a selectivity routine associated with every feasible
operator-class pair shown in table 3.1, and every operator will have two
selectivitiy routines associated with it \*- one for
ordinary restrictions, which are not used with index scans,
and the other for joins.
Each of these procedures is stored within appropriate tuple entries.
.pp
Thus, by executing the appropriate procedure with the appropriate parameters,
selectivity computation is flexible and simple.
A procedure written in pseudo C code that computes the selectivity of
the operator \*(lq>\*(rq for a B-tree index is shown in figure 3.6.
.(z
.hl
.(l
.sz \n(ep
.ft I
/*
 *    Procedure to compute the selectivity of the \*(lq>\*(rq operator
 *    when it is used with a B-tree index defined on integer fields.
 */
.ft R

float
greater_btree (opid, relid, attnos, values, flags, indexid, nkeys)
int    opid;        \fI/* contains unique id of operator \*(lq>\*(rq */\fR
int    relid;
int    attnos[];
int    values[];
int    flags[];        \fI/* equals 1 if clause is of the form `var > constant,'
             * else clause is of the form `constant > var'
             */\fR
int    indexid;    \fI/* parameter isn't used by this particular routine */\fR
int    nkeys;
{
    int    i;
    int    high;
    int    low;
    float    s;

    s = 1.0;
    \fBfor\fR (i = 0; i < nkeys; ++i) {
        high = retrieve high value of attribute `attnos[i]' in relation `relid';
        low = retrieve low value of attribute `attnos[i]' in relation `relid';
        \fI/*
         * the selectivity of multiple clauses is the product of the
         * selectivity of each individual clause
         */\fR
        \fBif\fR (flags[i] == 1)
            s = s * (high - values[i]) / (high - low);
        \fBelse\fR
            s = s * (values[i] - low) / (high - low);
    }
    \fBreturn\fR(s);
}
.sz \n(pp
.)l
.sp
.ce 2
\fBFigure 3.6\fR
Code to compute selectivity
.hl
.)z
.sh 2 "Nested-attribute Queries"
.pp
The last several subsections have described optimization of simple queries,
i.e. those without nested attributes.
Figure 3.7 summarizes information the optimizer uses in generating
possible query plans.
.(z
.hl
.sz \n(fp
.TS
center;
|c||c|c|c|c|c|c|c|
c ||c|c|c|c|c|c|c|.
_
OPER    operator    negator    commutator    msortop    hash    selectivity    join-selec
_
    =     \(!=    =     <    yes    \fIprocedures\fR    \fIprocedures\fR
    <    \(>=    >    no    no    \fIto compute\fR    \fIto compute\fR
    \(<=    >    \(>=    no    no    \fIselectivity\fR    \fIselectivity\fR
    >    \(<=    <    no    no    \fIof\fR    \fIof\fR
    \(>=    <    \(<=    no    no    \fI1-variable\fR    \fIjoin\fR
    AREAEQ    AREANEQ    AREAEQ    AREALT    yes    \fIclauses\fR    \fIclauses\fR
    AREALT    AREAGE    AREAGT    no    no    \fIcontaining\fR    \fIcontaining\fR
    AREALE    AREAGT    AREAGE    no    no    \fI\*(lqoperator\*(rq\fR    \fI\*(lqoperator\*(rq\fR
    AREAGT    AREALE    AREALT    no    no
    AREAGE    AREALT    AREALE    no    no
    _    _    _    _    _    _    _
.TE
.sp 2
.TS
center;
|c||c|c|c|c|c|
c ||c|c|c|c|c|.
_
AMOP    access-method    class    operator    selectivity    strategy \(dg
_
    B-tree    intops    =     \fIprocedures\fR    =
    B-tree    intops    <    \fIto compute\fR    <
    B-tree    intops    \(<=    \fIselectivity\fR    \(<=
    B-tree    intops    >    \fIof clauses\fR    >
    B-tree    intops    \(>=    \fIcontaining\fR    \(>=
    B-tree    areaops    AREAEQ    \fI\*(lqoperator\*(rq\fR    =
    B-tree    areaops    AREALT    \fIwhen used\fR    <
    B-tree    areaops    AREALE    \fIwith index\fR    \(<=
    B-tree    areaops    AREAGT    \fI\*(lqclass\*(rq\fR    >
    B-tree    areaops    AREAGE        \(>=
    hash    hashops    =         =
    B-tree    intops    <        sort
    B-tree    areaops    AREALT        sort
    _    _    _    _    _
.TE
.sp
.nf
$" " sup \(dg$ used in determining which operator corresponds to each generic operation (e.g., sorting)
.fi
.sz \n(pp
.sp
.ce 2
\fBFigure 3.7\fR
Summary of optimizer information stored in system catalogs
.hl
.)z
.pp
From here on, the module implementing the algorithms just described
will be called
the \*(lqsubplanner,\*(rq while the entire optimizer will be labeled the
\*(lqplanner\*(rq.
To create access plans for queries containing nested attributes,
the planner simply applies the subplanner algorithm
once for each nesting level of attributes in a query.
In other words, for any query, the number of times the subplanner is called
is equal to the maximum nesting of attributes in the query.
Once all subplanner calls have completed, the planner then builds a final
plan that indicates how these subpieces fit together.
Thus, given a query, the planner first modifies it to
consider only top level attributes.
This new query is passed to the subplanner to create a \fIsubplan\fR.
The planner then modifies the original query to consider only nested attributes.
This is recursively processed by the planner
to create a \fIplan\fR, and
the resulting access plan simply indicates which attributes
from \fIsubplan\fR and \fIplan\fR should be returned to the user.
.pp
An example will illustrate these ideas more clearly.
Suppose we have the following relation:
.(l
EMP ( name, dept, hobbies ),
.)l
where hobbies contains POSTQUEL queries to retrieve information about
the different hobbies each employee participates in.
One of these relations may be:
.(l
SOFTBALL ( empname, position, batting-history ),
.)l
where batting-history contains a POSTQUEL query retrieving information
about an employee's past batting averages from the relation:
.(l
BATTING-HIST ( empname, year, avg ).
.)l
Given the following query:
.(l
\fIQ1\fR: \fBretrieve\fR (EMP.name, EMP.hobbies.batting-history.avg) \fBwhere\fR
    EMP.hobbies.batting-history.year = \*(lq1986\*(rq \fBand\fR
    EMP.hobbies.position = \*(lqcatcher\*(rq \fBand\fR
    EMP.dept = DEPT.dname \fBand\fR
    DEPT.floor = 1,
.)l
which finds the current batting average of employees who are catchers and work
on the first floor,
the planner will first consider the top level of attributes by passing
the following query to subplanner:
.(l
\fIS1\fR: \fBretrieve\fR (EMP.name, EMP.hobbies) \fBwhere\fR
    EMP.dept = DEPT.dname \fBand\fR
    DEPT.floor = 1.
.)l
After the subplanner has optimized the above query,
the planner then only considers attributes beyond the top level nesting:
.(l
\fIQ2\fR: \fBretrieve\fR (EMP.hobbies.batting-history.avg) \fBwhere\fR
    EMP.hobbies.batting-history.year = \*(lq1986\*(rq \fBand\fR
    EMP.hobbies.position = \*(lqcatcher\*(rq
.)l
and passes this query to itself recursively.
This process is repeated, and in the process, the subplanner optimizes the
following two queries:
.(l
\fIS2\fR: \fBretrieve\fR (EMP.hobbies.batting-history) \fBwhere\fR
    EMP.hobbies.position = \*(lqcatcher\*(rq

\fIS3\fR: \fBretrieve\fR (EMP.hobbies.batting-history.avg) \fBwhere\fR
    EMP.hobbies.batting-history.year =\*(lq1986\*(rq
.)l
Since the maximum attribute nesting is three, recursion ends.
The final plan is constructed as shown in figure 3.8, where \fIPn\fR
is a subplan for executing subquery \fISn\fR.
\fIR2\fR is a node corresponding to \fIQ2\fR that indicates that
EMP.hobbies.batting-history.avg should be retrieved from \fIP3\fR,
and \fIR1\fR corresponds to \fIQ1\fR, indicating
that EMP.name should be retrieved from \fIP1\fR and
EMP.hobbies.batting-history.avg originates from \fIR2\fR.
.(z
.hl
.GS
file figure3.8
.GE
.sp
.ce 2
\fBFigure 3.8\fR
Structure of a query plan
.hl
.)z
.pp
To process this plan, the query executor first executes \fIP1\fR.
As soon as execution of \fIP1\fR returns a single tuple, \fIT\fR,
EMP.hobbies in that tuple is materialized into a temporary relation,
if that has not
already been done by POSTGRES's facility for preexecuting embedded queries.
The executor then processes the subtree whose root is \fIR2\fR in
a recursive manner for that instance of EMP.hobbies.
Each EMP.hobbies.batting-history.avg value returned from this
execution is combined
with EMP.name from \fIT\fR to create a result tuple that is passed to the
user.
When execution of \fIR2\fR has completed, \fIP1\fR is reexecuted to retrieve
another EMP.hobbies value that is used to process another instance
of the \fIR2\fR subtree.
This is repeated until all tuples from \fIP1\fR have been found.
The subtree \fIR2\fR is processed similarly.
\fIP2\fR is processed first, and \fIP3\fR is processed once for each
instance of a qualifying \fIP2\fR tuple.
.pp
Processing nested-attribute queries in this way is attractive because
it only requires a very clean extension of the basic optimization algorithm,
and nested attributes are transparent to the subplanner.
As a result, the code for query processing is also simpler.
Furthermore, entire query plans are generated a priori, eliminating the
need to optimize subqueries at runtime.
.pp
Optimizing nested-attribute queries a priori, however, does suffer because of
its simplicity.
In generating plans for higher nesting levels, the contents of relations that
will be
materialized from embedded queries are not known in advance.
Therefore, the optimizer does not know the sizes of these relations or the
distribution of values within nested attributes;
this information or some estimate
is normally required in computing subplan costs.
To work around this problem, the optimizer
simply assumes that materialized relations are
all of the same size, and if a nested attribute appears within a clause,
rather than return a parameter-dependent value for the selectivity,
the selectivity code
instead returns a constant that reflects the relative selectivities of various
operators.
For example, \*(lq=\*(rq is more selective than \*(lq>.\*(rq
So a clause containing \*(lq=\*(rq may have a selectivity of
$1 over 10$, while a clause with \*(lq>\*(rq
has a selectivity of $1 over 4$.
Although this may be an oversimplification, usually relations
materialized from embedded queries will be small.
So if the resulting plan is not the overall best choice in actuality,
the chosen plan will not be a bad plan.
.pp
As an alternative, pieces of nested-attribute queries can be optimized
at runtime.
This can be advantageous not only because relation sizes and attribute
distributions are known, but also
because it enables the optimizer to consider special paths.
For example, it may be possible to process an embedded query using
a B-tree index that sorts its records in ascending order.
If the tuples materialized from this query are later merge-sorted
using an ascending sort, due to the available index path,
the query processor need not explicitly sort the relation.
A runtime optimizer would be able to note this.
.pp
Although more intelligent query plans are generated,
there is a great deal of planning overhead associated with runtime
optimization.
For every tuple generated by \fIP1\fR, a subquery of the form:
.(l
\fBretrieve\fR (TEMP.batting-history.avg) \fBwhere\fR
    TEMP.batting-history.year = \*(lq1986\*(rq \fBand\fR
    TEMP.position = \*(lqcatcher\*(rq
.)l
must be optimized, where TEMP is the relation materialized from EMP.hobbies.
Subsequently, for every tuple generated by the above query, the following
query:
.(l
\fBretrieve\fR ($TEMP prime$.avg) \fBwhere\fR
    $TEMP prime$.year = \*(lq1986\*(rq
.)l
must also be optimized, where $TEMP prime$ is materialized from
TEMP.batting-history.
Due to this extra overhead, the efficiency of runtime
optimization is questionable.
.sh 2 "Query Plans"
.pp
The plan created by the optimizer is a tree of nodes.
Each node
corresponds to some scan, join, sort, or hash, or creation of a subresult.
Scan and join nodes contain information indicating which attributes
should be retrieved, which qualifications must be satisfied, and any other
information relevant to the particular type of scan or join.
Sort and hash nodes indicate which attributes should be placed into a
temporary and the operator used to perform the sort or hash.
A subresult node interconnects subplans and plans, indicating which attributes
should be retrieved and from where.
As an optimization, the topmost result node contains constant
qualifications, i.e. those without variables, so these clauses
can be examined prior to any other processing.
.pp
A possible (not necessarily the optimal) plan for the query introduced
in the previous subsection is shown in figure 3.9.
.(z
.hl
.GS
file figure3.9
.GE
.sp
.ce 2
\fBFigure 3.9\fR
Sample query plan tree
.hl
.)z
There are a few things about the tree that should be elaborated on to avoid
misconceptions.
First of all, the materialization steps shown
are not executed at runtime if the necessary embedded queries
have already been preexecuted, and their results remain valid.
Furthermore, as will become apparent later, these materialization steps
are actually implicit in the plan tree.
.pp
From the figure, it would appear that throughout the plan tree,
relation entries are explicitly
identified using relation and attribute names.
This would imply that the query processor would have to match identifiers
to locate values that originate from nodes elsewhere in the tree.
For example, references to TEMP1 and EMP attributes in the mergesort node
would be found by searching for an appropriate identifier within tuples
that originate from the two nodes below the mergesort node.
This, however, is not the case.
Explicit references are shown only for readability.
Rather, an attribute is identified by its
relative position within a specified tuple.
By using this relative value and a descriptor associated with tuples
returned by each node, the query
processor can locate a desired attribute instantaneously.
.pp
The names of temporaries associated with materialized relations, again,
are shown only for readability.
In the actual plan tree, these relations are identified by the attribute
containing the queries that will be used to build the temporary.
For example, TEMP2 would be identified by the relative attribute identifier
of TEMP1.hobbies, while TEMP3 would be identified by TEMP2.batting-history.
By examining the contents of these referenced attribute entries, the query
executor can determine whether materialization is necessary.
Thus, the materialization step is implicit in these attribute references.
.pp
For temporaries associated with sorts and hashes,
the name of the temporary shown in the tree serves merely as an
identifier.
It is left to the runtime executor to create the actual name.